#include <bits/stdc++.h>
using namespace std;
using uint=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
const int N=1e6+5;

// 递归快速幂
ll fastpow1(ll a, ll n, ll m) {
    if (n == 0) return 1 % m;
    a = a % m;
    ll t = fastpow1(a, n/2, m);
    if (n % 2 == 0) {
        return (t * t) % m;
    } else {
        return (t * t % m) * a % m;
    }
}

// 位运算快速幂
ll fastpow2(ll a, ll n, ll m) {
    ll ans = 1;
    a = a % m;
    while (n) {
        if (n & 1) {
            ans = (ans * a) % m;
        }
        a = (a * a) % m;
        n >>= 1;
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    
    ll a, n, m;
    cin >> a >> n >> m;
    
    // 测试两个快速幂函数
    ll res1 = fastpow1(a, n, m);
    ll res2 = fastpow2(a, n, m);
    
    cout << a << "^" << n << " mod " << m << " = " << res2 << endl;

    return 0;
}